Consider the problem of constructing a polar code of block length $N$ for thetransmission over a given channel $W$. Typically this requires to compute thereliability of all the $N$ synthetic channels and then to include those thatare sufficiently reliable. However, we know from [1], [2] that there is apartial order among the synthetic channels. Hence, it is natural to ask whetherwe can exploit it to reduce the computational burden of the constructionproblem. We show that, if we take advantage of the partial order [1], [2], we canconstruct a polar code by computing the reliability of roughly a fraction$1/\log^{3/2} N$ of the synthetic channels. In particular, we prove that$N/\log^{3/2} N$ is a lower bound on the number of synthetic channels to beconsidered and such a bound is tight up to a multiplicative factor $\log\logN$. This set of roughly $N/\log^{3/2} N$ synthetic channels is universal, inthe sense that it allows one to construct polar codes for any $W$, and it canbe identified by solving a maximum matching problem on a bipartite graph. Our proof technique consists of reducing the construction problem to theproblem of computing the maximum cardinality of an antichain for a suitablepartially ordered set. As such, this method is general and it can be used tofurther improve the complexity of the construction problem in case a newpartial order on the synthetic channels of polar codes is discovered.
展开▼
机译：考虑为在给定信道$ W $上的传输构造块长度为$ N $的极性码的问题。通常，这需要计算所有$ N $合成渠道的可靠性，然后包括足够可靠的渠道。但是，我们从[1]，[2]知道，合成通道之间存在分离顺序。因此，自然要问我们是否可以利用它来减轻施工问题的计算负担。我们证明，如果利用偏序[1]，[2]，我们可以通过计算合成通道的大约$ 1 / \ log ^ {3/2} N $的可靠性来构造极地码。特别地，我们证明了$ N / \ log ^ {3/2} N $是要考虑的合成通道数的下限，并且该上限严格到乘法因子$ \ log \ logN $。这套大约$ N / \ log ^ {3/2} N $的合成通道是通用的，从某种意义上讲，它允许为任何$ W $构造极性码，并且可以通过解决最大匹配问题来识别。二分图。我们的证明技术包括将构造问题简化为针对合适的部分有序集计算反链的最大基数的问题。这样，该方法是通用的，并且如果在极性码的合成通道上发现了新的偏序，则可以用于进一步改善构造问题的复杂性。
展开▼
